package uestc.lj.basic.tree;

import java.util.LinkedList;

/**
 * 判断二叉树是否是一颗搜索二叉树
 *
 * @Author:Crazlee
 * @Date:2021/11/23
 */
public class Code05_IsBST {
	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static boolean isBST(Node head) {
		if (head == null) {
			return true;
		}
		LinkedList<Node> list = new LinkedList<>();
		process(head, list);
		int result = Integer.MIN_VALUE;
		for (Node node : list) {
			if (result >= node.value) {
				return false;
			}
			result = node.value;
		}
		return true;
	}

	private static void process(Node head, LinkedList<Node> list) {
		if (head == null) {
			return;
		}
		process(head.left, list);
		list.add(head);
		process(head.right, list);
	}

	public static int preValue = Integer.MIN_VALUE;

	public static boolean checkBST(Node head) {
		if (head == null) {
			return true;
		}
		boolean isLeftBST = checkBST(head.left);
		if (!isLeftBST) {
			return false;
		}
		if (head.value <= preValue) {
			return false;
		} else {
			preValue = head.value;
		}
		return checkBST(head.right);
	}


	public static boolean isBST2(Node head) {
		if (head == null) {
			return true;
		}
		return process(head).isBST;
	}

	public static class ReturnData {
		int min;
		int max;
		boolean isBST;

		public ReturnData(int min, int max, boolean isBST) {
			this.min = min;
			this.max = max;
			this.isBST = isBST;
		}
	}

	public static ReturnData process(Node head) {
		if (head == null) {
			return null;
		}
		ReturnData left = process(head.left);
		ReturnData right = process(head.right);
		int min = head.value;
		int max = head.value;
		if (left != null) {
			min = Math.min(min, left.min);
			max = Math.max(max, left.max);
		}
		if (right != null) {
			min = Math.min(min, right.min);
			max = Math.max(max, right.max);
		}
		boolean isBST = true;
		if (left != null && (!left.isBST || left.max > head.value)) {
			isBST = false;
		}
		if (right != null && (!right.isBST || right.min < head.value)) {
			isBST = false;
		}
		return new ReturnData(min, max, isBST);
	}
}
